#ifndef AC_DFA_H
#define AC_DFA_H

#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<cstdio>

struct KeywordInfo
{
    //当前关键字的类型
    int type;
    //当前关键字的子类型
    int subtype;
    //当前的关键字
    std::string value;
    //当前关键字所对应的信息，可以是一个类指针也可以是其他的
    void *ptr;
    //指向下一个关键字
    int next;

};

class AC_DFA
{
public:
	AC_DFA();

	//没有没有析构函数，因为编译器会替我们合成一个
	~AC_DFA();

	//得到关键字的个数
	unsigned int GetKeywordsNumber();

	//添加关键字
	void AddKeyword(const std::string& word, int type, int subtype, void *ptr);

    const std::string& GetKeywords(int index);

    void * GetAddon(int index);
    //返回第index关键字所连接的下一个关键字
    int GetNext(int index);

    int GetType(int index);

    int GetSubType(int index);

	//构建自动机
	void BuildAll();

	//查找str内容,匹配找到的关键字
	char * Find(const std::string& content, int& index);

    char * Find(const char *content, int &index);

    //在[content,content+len]范围里查找
    char *Find4Len(const char *content, int &index, unsigned int len);

    //精确匹配该关键字,匹配的条件：
    //1.内容一样
    //2.长度一样
    char *Find4Exact(const char *content, int &index, unsigned int len);

	void ShowKeywords();

	//Debug时显示状态转换图
	void ShowAll();

private:
	//构建状态转换图
	void BuildStep1();

	//利用fail函数修改状态转换图
	void BuildStep2();

	//Goto状态转换图
	std::vector<std::vector<int> > Goto;
	
	//总共拥有的状态数
	int TotolStates;

	//关键字列表	
	std::vector<KeywordInfo> Keywords;

	//ASCII表的256个字符
	static const int ASC=256;
	//Output在Goto表中的位置
	static const int OUTPUT=256;

};

inline AC_DFA::AC_DFA()
{
    TotolStates=0;
}
	//没有没有析构函数，因为编译器会替我们合成一个
inline AC_DFA::~AC_DFA()
{
}

	//得到关键字的个数
inline unsigned int AC_DFA::GetKeywordsNumber()
{
    return Keywords.size();
}

	//添加关键字
inline void AC_DFA::AddKeyword(const std::string& word, int type, int subtype, void *ptr)
{
    KeywordInfo info={type,subtype,word,ptr,-1};
    Keywords.push_back(info);
}

inline const std::string& AC_DFA::GetKeywords(int index)
{
    return Keywords[index].value;
}

inline void * AC_DFA::GetAddon(int index)
{
    return Keywords[index].ptr;
}

    //返回第index关键字所连接的下一个关键字
inline int AC_DFA::GetNext(int index)
{
    return Keywords[index].next;
}

inline int AC_DFA::GetType(int index)
{
    return Keywords[index].type;
}

inline int AC_DFA::GetSubType(int index)
{
    return Keywords[index].subtype;
}

	//构建自动机
inline void AC_DFA::BuildAll()
{
    BuildStep1();
    ShowAll();
    BuildStep2();
    ShowAll();

}

	//查找str内容,匹配找到的关键字
inline char * AC_DFA::Find(const std::string& content, int& index)
{
    return Find(content.c_str(),index);
}

inline void AC_DFA::ShowKeywords()
{
    std::cout<<std::endl<<"---------------------Keywords--------------------"<<std::endl;
    for(unsigned int i=0; i<Keywords.size(); ++i)
        std::cout<<"ID:"<<i<<" "<<Keywords[i].value<<" "
            <<Keywords[i].value.size()<<" "<<Keywords[i].type<<" "
            <<Keywords[i].subtype<<" "<<Keywords[i].ptr<<std::endl;
    std::cout<<std::endl;
}

	//Debug时显示状态转换图
inline void AC_DFA::ShowAll()
{
#ifdef _DEBUG
    std::printf("---------------Goto-------------\n");
    for(int i=0; i<Goto.size(); ++i)
    {
        std::printf("State %02d:   ",i);
        for(int j=0; j<OUTPUT; ++j)
        {
            if(Goto[i][j]!=0)
                std::printf("%c:%d ",j,Goto[i][j]);
        }
        if(Goto[i][OUTPUT]>0)
            std::printf("OUTPUT:%d",Goto[i][OUTPUT]);

        std::printf("\n");
    }
#endif
}

#endif
